package 力扣日常刷题.木22一月.第10天0118;

/**
 * @author 帅小伙
 * @date 2022/1/18
 * @description
 */
public class Demo26动态规划中等完全平方数 {

    public int numSquares(int n) {
        int[] dp = new int[n+1];

        for (int i = 1; i <= n ; i++) {
            int min = Integer.MAX_VALUE;
            for (int j = 1; j*j <=i ; j++) {
                min = Math.min(min,dp[i-j*j]);
            }
            dp[i] = min+1;
        }
        return dp[n];
    }
}
